package com.learn.algorlthm;

/**
 * @classname:
 * @Description:数字在排序数组中出现的次数
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-08-14 17:24
 */
public class Learn53 {

    public static int getNumberOfK(int[] nums, int K) {

        int first = binarySearch(nums, K);
        int last = binarySearch(nums, K + 1);
        return (nums[first] != K || first == nums.length) ? 0 : last-first;
    }

    private static int binarySearch(int[] nums, int K) {
        int s = 0, e = nums.length;

        while (s < e) {
            int m = s + (e - s)/2;
            if (nums[m] <= K)
                e = m;
            else
                s = m+1;
        }

        return s;
    }
}
